First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,

• Given [1,2,0] return 3,
  
• and [3,4,-1,1] return 2.
  Your algorithm should run in O(n) time and uses constant space.

题目大意：给定一个未排序的数组，找到第一个缺少的正数数，要求时间O(N),空间O(1)

题目难度：Hard

/**
 * Created by gzdaijie on 16/5/21
 * 首先可以确定,丢失的正数不超过 length,那可以在数组上标记某个数是否丢失了
 * 第一次遍历,删除小于等于0 或大于等于length的数
 * 第二次遍历,将num[num[i] - 1]加2n,即nums[2] > n表示2出现过了,因为加上n后,可以仍可取余判断代表哪个正数
 * 第三次遍历，找到第一个小于2len的位置 k, 则证明k+1没有出现过
 */
public class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) return 1;

        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] < 0 || nums[i] > len) nums[i] = 0;
        }

        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                nums[(nums[i] - 1) % len] += 2 * len;
            }
        }

        int k = -1;
        while (++k < len && nums[k] > len); /* empty */
        return k + 1;
    }
}